#include "aatree.h"
#include <stdlib.h>
#include "fatal.h"

/* START: fig12_27.txt */
/* Returned for failures */
Position NullNode = NULL; /* Needs more initialization */

struct AANode
{
    ElementType Element;
    AATree Left;
    AATree Right;
    int Level;
};

AATree
Initialize(void)
{
    if (NullNode == NULL)
    {
        NullNode = malloc(sizeof(struct AANode));
        if (NullNode == NULL)
            FatalError("Out of space!!!");
        NullNode->Left = NullNode->Right = NullNode;
        NullNode->Level = 0;
    }
    return NullNode;
}
/* END */

AATree
MakeEmpty(AATree T)
{
    if (T != NullNode)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NullNode;
}

Position
Find(ElementType X, AATree T)
{
    if (T == NullNode)
        return NullNode;
    if (X < T->Element)
        return Find(X, T->Left);
    else if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

Position
FindMin(AATree T)
{
    if (T == NullNode)
        return NullNode;
    else if (T->Left == NullNode)
        return T;
    else
        return FindMin(T->Left);
}

Position
FindMax(AATree T)
{
    if (T != NullNode)
        while (T->Right != NullNode)
            T = T->Right;

    return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position
SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    return K1; /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position
SingleRotateWithRight(Position K1)
{
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    return K2; /* New root */
}

/* START: fig12_29.txt */
/* If T's left child is on the same level as T, */
/* perform a rotation */

AATree
Skew(AATree T)
{
    if (T->Left->Level == T->Level)
        T = SingleRotateWithLeft(T);
    return T;
}

/* If T's rightmost grandchild is on the same level, */
/* rotate right child up */

AATree
Split(AATree T)
{
    if (T->Right->Right->Level == T->Level)
    {
        T = SingleRotateWithRight(T);
        T->Level++;
    }
    return T;
}
/* END */

/* START: fig12_36.txt */
AATree
Insert(ElementType Item, AATree T)
{
    if (T == NullNode)
    {
        /* Create and return a one-node tree */
        T = malloc(sizeof(struct AANode));
        if (T == NULL)
            FatalError("Out of space!!!");
        else
        {
            T->Element = Item;
            T->Level = 1;
            T->Left = T->Right = NullNode;
        }
    }
    else if (Item < T->Element)
        T->Left = Insert(Item, T->Left);
    else if (Item > T->Element)
        T->Right = Insert(Item, T->Right);

    /* Otherwise it's a duplicate; do nothing */

    T = Skew(T);
    T = Split(T);
    return T;
}
/* END */

/* START: fig12_38.txt */
AATree
Remove(ElementType Item, AATree T)
{
    static Position DeletePtr, LastPtr;

    if (T != NullNode)
    {
        /* Step 1: Search down tree */
        /*         set LastPtr and DeletePtr */
        LastPtr = T;
        if (Item < T->Element)
            T->Left = Remove(Item, T->Left);
        else
        {
            DeletePtr = T;
            T->Right = Remove(Item, T->Right);
        }

        /* Step 2: If at the bottom of the tree and */
        /*         item is present, we remove it */
        if (T == LastPtr)
        {
            if (DeletePtr != NullNode &&
                Item == DeletePtr->Element)
            {
                DeletePtr->Element = T->Element;
                DeletePtr = NullNode;
                T = T->Right;
                free(LastPtr);
            }
        }

        /* Step 3: Otherwise, we are not at the bottom; */
        /*         rebalance */
        else if (T->Left->Level < T->Level - 1 ||
                 T->Right->Level < T->Level - 1)
        {
            if (T->Right->Level > --T->Level)
                T->Right->Level = T->Level;
            T = Skew(T);
            T->Right = Skew(T->Right);
            T->Right->Right = Skew(T->Right->Right);
            T = Split(T);
            T->Right = Split(T->Right);
        }
    }
    return T;
}
/* END */

ElementType
Retrieve(Position P)
{
    return P->Element;
}
